package com.my.algorithmlearning.leetcode;

import com.my.algorithmlearning.entity.ListNode;

/**
 * @ClassName Medium_148_MerSortLinkedList
 * @Description https://leetcode.cn/problems/sort-list/solution/zhong-deng-148-pai-xu-lian-biao-he-bing-3ymhg/
 * 参考https://leetcode.cn/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/
 * @Author wanghaiwei
 * @Date 2023/5/5 11:19
 */
public class Medium_148_MerSortLinkedList {
    public static void main(String[] args) {
        Medium_148_MerSortLinkedList solution = new Medium_148_MerSortLinkedList();
        ListNode listNode = ListNode.convertArrayToListNode(new int[]{4, 2, 1, 3});
        listNode.clearEndFlag();
        System.out.println(solution.sortList(listNode));
    }

    public ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        //找到中点位置
        ListNode midNode = locateMiddleNode(head);
        ListNode leftHead = head;
        ListNode rightHead = midNode;
        //断开链表，彻底分成两部分
        ListNode leftEnd = leftHead;
        while (leftEnd.next != midNode) {
            leftEnd = leftEnd.next;
        }
        leftEnd.next = null;
        //分治
        ListNode leftPartResult = sortList(leftHead);
        ListNode rightPartResult = sortList(rightHead);
        return mergeSort(leftPartResult, rightPartResult);
    }

    public ListNode mergeSort(ListNode leftHead, ListNode rightHead) {
        ListNode resultHead = new ListNode();
        ListNode curr = resultHead;
        while (leftHead != null && rightHead != null) {
            if (leftHead.val <= rightHead.val) {
                curr.next = leftHead;
                leftHead = leftHead.next;
            } else {
                curr.next = rightHead;
                rightHead = rightHead.next;
            }
            curr = curr.next;
        }
        curr.next = leftHead == null ? rightHead : leftHead;
        return resultHead.next;
    }

    private ListNode locateMiddleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
